package com.cat.graphTheory;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution44 {
    static int N = 11; // 顶点数最大为10，数组稍大些
    static int[][] arr = new int[N * N][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(System.out);

        // 读取顶点数n和边数m
        st.nextToken();
        int n = (int) st.nval;
        st.nextToken();
        int m = (int) st.nval;

        // 读取m条边
        for (int i = 0; i < m; i++) {
            st.nextToken();
            int u = (int) st.nval;
            st.nextToken();
            int v = (int) st.nval;
            arr[i] = new int[]{u - 1, v - 1};
        }
        int ans = m, sum;
        for (int i = 0; i < 1 << n - 1; i++) {
            sum = 0;
            for (int j = 0; j < m; j++) {
                var e = arr[j];
                if ((i >> e[0] & 1) == (i >> e[1] & 1)) {
                    sum++;
                }
            }
//            out.println(sum);
            ans = Math.min(ans, sum);
        }
        out.println(ans);
        out.flush();
        out.close();
        br.close();
    }
}
